Red-Black Tree

contents

표준 자료구조의 "최종 보스"에 오신 것을 환영합니다.

거의 모든 주요 프로그래밍 언어나 운영체제의 내부를 들여다보면 레드-블랙 트리(Red-Black Tree) 를 발견할 수 있습니다. Java의 TreeMap과 TreeSet, Java HashMap의 내부 구조(버킷 충돌 시), C++의 std::map, 심지어 리눅스 커널의 프로세스 스케줄러까지 구동하는 핵심 기술입니다.

이전 설명에서 우리는 AVL 트리가 엄격하게 균형을 맞추기 때문에 탐색에는 믿을 수 없을 정도로 빠르지만, 끊임없이 "회전(Rotations)"을 해야 하므로 삽입/삭제에는 다소 느리다는 것을 알았습니다.

레드-블랙 트리(RBT) 는 업계가 찾은 궁극의 타협점입니다. 이것은 느슨하게 균형을 맞춘(loosely balanced) 이진 탐색 트리입니다. 균형 유지 규칙을 아주 살짝 완화함으로써 데이터를 쓸 때 필요한 회전 횟수를 대폭 줄이면서도, 여전히 번개처럼 빠른 $O(\log n)$의 읽기 속도를 보장합니다.

어떻게 이 완벽한 밸런스를 맞추는지에 대한 상세한 분석입니다.

1. 레드-블랙 트리의 5가지 절대 규칙

AVL 트리처럼 좌우의 "높이"를 수치로 계산하는 대신, RBT는 모든 노드를 빨간색(Red) 또는 검은색(Black) 으로 칠합니다.

유효한 레드-블랙 트리가 되려면 다음 5가지 규칙을 엄격하게 준수해야 합니다:

1. 색상 규칙: 모든 노드는 빨간색이거나 검은색이다.
2. 루트 규칙: 루트(Root) 노드는 항상 검은색이다.
3. 리프 규칙: 모든 빈 단말 노드(맨 아래의 NIL 또는 null 노드)는 검은색으로 간주한다.
4. 빨간색 규칙 (이중 빨강 금지): 빨간색 노드의 자식은 반드시 모두 검은색이어야 한다. 즉, 빨간색 노드 두 개가 연속으로(부모-자식 관계로) 연결될 수 없다.
5. 블랙 높이(Black-Height) 규칙: 어떤 특정 노드에서부터 그 아래의 모든 NIL 리프 노드까지 내려가는 모든 경로에는 정확히 같은 개수의 검은색 노드가 있어야 한다.

이 규칙들이 왜 중요할까요?

규칙 4와 5가 함께 작용하여 "느슨한 균형"을 만들어냅니다.

• 바닥까지 가는 가장 짧은 경로는 모든 노드가 '검은색'으로만 이루어졌을 때입니다.
• 가장 긴 경로는 '빨강-검정-빨강-검정'이 번갈아 나타날 때입니다 (규칙 4에 의해 빨간색이 연속될 수 없으므로).
• 모든 경로는 반드시 같은 수의 검은색 노드를 가져야 하므로 (규칙 5), 가장 긴 경로는 절대 가장 짧은 경로의 두 배를 넘을 수 없습니다. 트리가 약간 찌그러져 보일 수는 있지만, 연산 속도를 $O(\log n)$으로 유지할 수 있을 만큼 충분히 균형 잡혀 있음이 수학적으로 보장됩니다.

2. 삽입 작동 원리 (The Mechanics)

레드-블랙 트리에 새로운 숫자를 삽입할 때는 일반적인 이진 탐색 트리의 규칙(작으면 왼쪽, 크면 오른쪽)을 따릅니다.

삽입의 절대 규칙: 새로 삽입되는 노드는 무조건 빨간색(RED)으로 칠해집니다.

• 왜 그럴까요? 만약 검은색으로 칠한다면, 그 노드가 추가된 특정 경로만 검은색 노드가 하나 더 많아지므로 규칙 5(블랙 높이 규칙)를 즉시 위반하게 됩니다. 빨간색 노드를 삽입하면 블랙 높이가 그대로 유지됩니다.

하지만 빨간색 노드를 삽입했을 때, 그 부모 노드 역시 빨간색이라면 규칙 4(이중 빨강 금지)를 위반하게 됩니다. 이럴 경우 트리를 수정해야 합니다.

해결책: "삼촌(Uncle)" 노드를 확인하라

"이중 빨강(Double Red)" 위반을 해결하기 위해, 트리는 새로 삽입된 노드의 삼촌(부모의 형제 노드) 이 무슨 색인지 확인합니다.

케이스 1: 삼촌이 빨간색(RED)일 때 $\rightarrow$ 색상 변경(Recolor)!

• 동작: 회전할 필요가 없습니다. 부모와 삼촌의 색상을 검은색으로 바꾸고, 조부모(할아버지) 노드를 빨간색으로 바꿉니다.
• 참고: 만약 조부모 노드가 루트(Root)라면 규칙 2에 의해 다시 검은색으로 칠해집니다.

케이스 2: 삼촌이 검은색(BLACK)이거나 NIL이고, 노드들이 삼각형(지그재그) 모양일 때

• 동작: 삼각형을 일직선으로 펴기 위해 부모 노드를 기준으로 회전합니다. 이렇게 하면 완벽하게 케이스 3의 형태로 넘어갑니다.

케이스 3: 삼촌이 검은색(BLACK)이거나 NIL이고, 노드들이 일직선 모양일 때

• 동작: 조부모 노드를 기준으로 회전합니다. 그다음, 부모와 조부모의 색상을 서로 바꿉니다(Swap). 위반이 해결되었습니다!

3. 삭제 (가장 어려운 부분)

레드-블랙 트리의 삭제 연산은 학부 컴퓨터 과학 과정에서 가장 복잡한 알고리즘 중 하나로 악명이 높습니다. 무려 6가지의 다른 케이스를 포함합니다.

핵심 논리는 이렇습니다: 빨간색 노드를 지우면 트리에 아무 문제가 없습니다. 하지만 검은색 노드를 지우게 되면, 해당 경로의 블랙 높이 규칙(규칙 5)이 깨져버립니다. 그러면 트리는 균형이 복구될 때까지 형제 노드들로부터 "검은색 속성(blackness)"을 빌려오기 위해 매우 복잡한 색상 전환과 회전을 연쇄적으로 수행해야만 합니다. (다행히도 우리는 이 골치 아픈 과정을 직접 짜지 않고 언어의 표준 라이브러리에게 맡깁니다!)

4. 요약: AVL 트리 vs. 레드-블랙 트리

references